package leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/21 0021.
 */
public class Subsets {
    LinkedList<Integer> list = new LinkedList<Integer>();
    LinkedList<List<Integer>> rst = new LinkedList<List<Integer>>();
    private void sub(int[] S,int begin){
        if(begin>=S.length){
            rst.add((List<Integer>) list.clone());
            return ;
        }
        rst.add((List<Integer>) list.clone());
        for (int i=begin;i<S.length;i++){
            list.add(S[i]);
            sub(S,i+1);
            list.removeLast();
        }
    }
    public List<List<Integer>> subsets(int[] S) {
        if(S==null || S.length==0){
            rst.add(new LinkedList<Integer>());
            return rst;
        }
        Arrays.sort(S);
        sub(S, 0);
        return rst;
    }
    public static void main(String[] args){
        Subsets subsets = new Subsets();
        int[] S = {1};
        LinkedList<List<Integer>> list = (LinkedList<List<Integer>>) subsets.subsets(S);
        for(List list1:list){
//            for(Object o:list1){
//                System.out.print(" "+o);
//            }
            System.out.println(list1);
        }
    }
}
